The present invention relates to networking technology, and more particularly, to network switches.
In a digital communication system, a local area network (LAN) may be connected to another LAN by way of a switch (bridge). LANs are typically packet-based, in which messages are broken into packets (frames). Many LANs are based on IEEE (Institute of Electrical and Electronic Engineers) standard 802.3, commonly called Ethernet. FIG. 1 illustrates four-port switch 102 connecting four Ethernet segments 104, 106, 108, and 110. Each Ethernet segment may be operated at different speeds. For example, segment 102 may be a 10 Mbit Ethernet whereas the other segments may be 100 Mbit Ethernets. Connected to each Ethernet segment are various data terminal equipment (DTE), which may be clients, servers, or other users and creators of digital data. Each DTE has one or more media access control (MAC) devices connected to an Ethernet segment, where each MAC has a unique address.
An Ethernet packet (frame) along with some of its fields is illustrated in FIG. 2. Shown are destination address field 202, source address field 204, frame check sequence field 206, and preamble field 208. The payload data for the Ethernet packet of FIG. 2 is indicated by 210. Not all of the fields are shown. The source address field of an Ethernet packet provides the address of the MAC source of the packet, and the destination address field provides the MAC address of the packet""s intended recipient.
Switch 102 forwards or filters a packet based upon the packet""s source and destination address fields. For example, if the source of a data packet is DTE 112 and its destination is DTE 114, then switch 102 filters out the data packet, i.e., it is not forwarded to another Ethernet segment. However, if the source of a data packet is DTE 112 and its destination is DTE 116, then the packet is forwarded to Ethernet segment 108.
Usually, a table is accessed by switch 102 to determine whether a packet is forwarded or filtered. Given an address, a table entry provides the segment (or equivalently, the switch port connected to the segment) containing the address, provided the table entry is present in the table. Additional information stored in the table may be the age of the address entry, so that updates based upon age may be performed. The table is built up through a learning process. For example, by observing the source addresses of data packets, switch 102 learns which segments have which MAC addresses. If a data packet is received in which its destination address is not present in a table, switch 102 floods the network with the data packet, i.e., it is forwarded to all segments.
A table may be implemented by a content addressable memory (CAM), whereby an address is matched with stored addresses, and if there is a hit, the appropriate information, such as a switch port, is retrieved. Data structures (or abstract data types) other than tables may be used to associate addresses with segments (switch ports). For example, binary trees, or Patricia trees, may be utilized. However, MAC addresses are 48 bits, and typically a design goal is to provide a capacity of 8 K addresses. Prior techniques of utilizing CAMs and trees may be costly in terms of silicon area or speed. The present invention is motivated to address some or all of these problems.
In one embodiment of the present invention, a switch comprises a memory unit to store a hash table having entries. Each entry in the hash table is pointed to by a hash table address, and has an address field to indicate an address and a switch port field to indicate a switch port. The hash table address is a portion of the coefficients of a remainder polynomial obtained by dividing the polynomial sum of an address polynomial and a shifted key polynomial by a generator polynomial.